5.3 Planar Maps (planar_map)

1. Definition

An instance M of the data type planar$\_map$ is the combinatorial embedding of a planar graph.


2. Creation

M (graph G)

creates an instance M of type planar$\_map$ and initializes it to the planar map represented by the directed graph G. G represents an undirected planar map, i.e. for every edge (v, w) in G the reverse edge (w, v) is also in G and there is a planar embedding of G such that for every node v the ordering of the edges in the adjacency list of v corresponds to the counter-clockwise ordering of these edges around v in the embedding.


3. Operations


Most operations are the same as for directed graphs. The following operations are either additional or have different effects.


& truecm & truecm & face adj_face edge e returns the face of to the right of e.

listface all_faces returns the list of all faces of .

listface adj_faces node v returns the list of all faces of adjacent to node v in counter-clockwise order.

listedge adj_edges face f returns the list of all edges of bounding face f in clockwise order.

listnode adj_nodes face f returns the list of all nodes of adjacent to face f in clockwise order.

edge reverse edge e returns the reversal of edge e in .

edge first_face_edge returns the first edge of face f in .

edge succ_face_edge edge e returns the successor edge of e in face f i.e., the next edge in clockwise order.

edge pred_face_edge edge e returns the predecessor edge of e in face f, i.e., the next edge in counter-clockwise order.

edge new_edge edge e_1, edge e_2 inserts the edge e = (source(e1), source(e2)) and its reversal edge into M. e1 and e2 are bounding the same face F. The operation splits F into two new faces.

edge del_edge edge e deletes the edge e from . The two faces adjacent to e are united to one face.

edge split_edge edge e splits edge e = (v, w) and its reversal r = (w, v) into edges (v, u), (u, w), (w, u), and (u, v). Returns the edge (u, w).

node new_node face f splits face f into triangles by inserting a new node u and connecting it to all nodes of f. Returns u.

node new_node listedge el splits the face bounded by the edges in el by inserting a new node u and connecting it to all source nodes of edges in el. all edges in el bound the same face.

listedge triangulate triangulates all faces of by inserting new edges. The list of inserted edges is is returned.

int straight_line_embedding node_array(int) xcoord, node_array(int) ycoord computes a straight line embedding for M with integer coordinates xcoord[v], ycoord[v]) in the range 0...2(n - 1) for every node v of M, and returns the maximal used coordinate.


4. Iteration

forall_faces(f, M) { ``the faces of M are successively assigned to f" }

forall_adj_edges(e, f) { ``the edges adjacent to face f are successively assigned to e" }


5. Implementation

Planar maps are implemented by parameterized directed graphs. All operations take constant time, except of, new_edge and del_edge which take time O(f ) where f is the number of edges in the created faces, and triangulate and straight_line_embedding take time O(n) where n is the current size (number of edges) of the planar map.